package com.arron.algorithm;

import java.util.HashMap;
import java.util.Map;

public class LRUCache {


    Map<Integer,Node> map;

    Node head;
    Node tail;

    int capacity;
    int size;


    class Node{
        int k;
        int v;
        Node pre;
        Node next;

        public Node(){

        }

        public Node(int k,int v){
                this.k = k;
                this.v = v;
        }
    }

    LRUCache(int capacity) {

        this.capacity = capacity;
        map = new HashMap<>(capacity);
        head = new Node();
        tail = new Node();
        head.next = tail;
        tail.pre = head;

    }

    int get(int key) {

        Node node = map.get(key);
        if (node != null){
            removeNode(node);
            addNodeToHead(node);

            return node.v;
        }
        return -1;
    }

    void put(int key, int value) {

        Node node = map.get(key);

        if (node == null){
             node = new Node(key,value);
            size++;
            if (size > this.capacity){
                Node pre = tail.pre;
                //删除尾节点
                removeNode(pre);
                // 添加节点到头部
                addNodeToHead(node);

                map.remove(pre.k);
                size--;
            }else {

                // 直接添加到头节点
                addNodeToHead(node);
            }
            map.put(key,node);
        }else {
            // 先将原来的节点删除
            removeNode(node);
            // 将节点添加到头部
            addNodeToHead(node);
            node.v = value;
        }


    }

    private void addNodeToHead(Node node) {
        head.next.pre = node;
        node.pre = head;
        node.next = head.next;
        head.next = node;
    }

    private void removeNode(Node node) {

        node.pre.next = node.next;
        node.next.pre = node.pre;

        node.pre = null;
        node.next = null;

    }


    public static void main(String[] args) {
        LRUCache cache = new LRUCache(3);
        cache.put(1,3);
        cache.put(2,4);
        cache.put(3,5);

        cache.get(1);
        cache.get(2);

        cache.put(10,24);
        System.out.println(cache.get(3));
        System.out.println(cache);
    }


}
